/**
 * 438. 找到字符串中所有字母异位词
 * https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
 */
const { displayBaseArray } = require('../../libs/public');

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
function findAnagrams(s, p) {
  const cache = new Array(128);
  let { length } = p;
  for (let i = 0; i < length; i += 1) {
    const code = p.charCodeAt(i);
    cache[code] = (cache[code] || 0) + 1;
  }
  const result = [];
  const lastIndex = s.length - p.length;
  for (let i = 0; i <= lastIndex;) {
    for (let j = i; j < s.length; j += 1) {
      const code = s.charCodeAt(j);
      if (cache[code] === undefined) {
        for (let k = i; k < j; k += 1) {
          cache[s.charCodeAt(k)] += 1;
          length += 1;
        }
        i = j + 1;
        break;
      }
      if (!cache[code]) {
        for (let k = i; k < j; k += 1) {
          const kCode = s.charCodeAt(k);
          cache[kCode] += 1;
          length += 1;
          if (kCode === code) {
            i = k + 1;
            break;
          }
        }
      }
      cache[code] -= 1;
      length -= 1;
      if (!length) {
        result.push(i);
        cache[s.charCodeAt(i)] += 1;
        length += 1;
        i += 1;
      }
    }
  }
  return result;
}

console.log(displayBaseArray(findAnagrams('cbaebabacd', 'abc')) === '[0,6]');
console.log(displayBaseArray(findAnagrams('abab', 'ab')) === '[0,1,2]');
